Skip to main content
Home
Mentions
Analytics
Upload

    A Survey of Behaviour Trees and their Applications for Game AI A Survey of Behaviour Trees and their Applications for Game AI

    By Kim McQuillan
    visibility

    1343 Views

    description

    19 Pages

    link1 File ▾
    sell
    Artificial Intelligence,
    Video Game Design

    Behaviour Trees are relatively new, intuitive and versatile tools for Game Artificial Intelligence (Game AI). While they have been utilized in the development of a few major game releases, the commercial gaming industry is yet to harness their full potential. This paper will examine what behaviour trees are within the context of Game AI, and provide an overview of their potential applications within the field. It will achieve this end by surveying a range of academic books, journal and conference papers relevant to Game AI in general, and behaviour trees in particular. By describing the ease of use, versatility, and potential capabilities of behaviour trees, it is hoped that this paper will help to facilitate increased familiarity with, and further appreciation for, behaviour trees among current and future game developers.

    ... Read more
    A Survey of Behaviour Trees and their Applications for Game AI by Kim McQuillan James Cook University CP5330 SP2 2015 Special Interest Topic 1: Intelligent Agents & Simulation Word Count: 5349
    Page 1 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan Abstract: Behaviour Trees are relatively new, intuitive and versatile tools for Game Artificial Intelligence (Game AI). While they have been utilized in the development of a few major game releases, the commercial gaming industry is yet to harness their full potential. This paper will examine what behaviour trees are within the context of Game AI, and provide an overview of their potential applications within the field. It will achieve this end by surveying a range of academic books, journal and conference papers relevant to Game AI in general, and behaviour trees in particular. By describing the ease of use, versatility, and potential capabilities of behaviour trees, it is hoped that this paper will help to facilitate increased familiarity with, and further appreciation for, behaviour trees among current and future game developers. 1. Introduction: As games become more sophisticated, due to advances in computing power, graphics and physics, so does the Game AI toolkit (Child & Dey, 2013). Behaviour Trees are a relatively recent example of intuitive and versatile tools for Game AI (Kirby, 2011). While they are beginning to be embraced commercially for some applications, their potential is yet to be fully harnessed, with most commercial Game AI still generated by hard-coded scripts (Černý, Plch, Marko, Gemrot, Ondráček, & Brom, 2015). This paper will examine the nature, potential applications, benefits, limitations and trends of behaviour trees, beginning with some general background about Game AI and decision-making. 1.1 AI for Games 1.1.1 Definition Kirby (2011) defines Game AI as “the ability to act intelligently under changing conditions”. While it aims to make automated decisions within a game appear intelligent, a bigger challenge is preventing those decisions from, at times, appearing stupidity. This is known as “avoiding artificial stupidity” (Kirby, 2011). Interestingly, even random decisions can give a player the impression of an intelligent, ‘learning’ AI; testament that complexity is not a goal in itself; simple systems will often suffice (Kirby, 2011). 1.1.2 Role in Game Development A game is an entertainment product that relies on limited resources, therefore every element should contribute to maximizing player enjoyment (Kirby, 2011). It follows that the aim of Game AI is to enhance player experience (Johansson & Dell'Acqua, 2012). AI actions must be noticeable to the player, else they represent no more than computational waste (Kirby, 2011). This does not always mean the player needs to witness intelligent behaviour at the exact moment of AI decision-making, however it should be evident at some point, and enhance the playing experience in some way (Kirby, 2011). This could be via realistic, appropriately stylized, or simply entertaining AI behaviours, evoking player emotions, or simply aiding the suspension of disbelief in a game narrative.
    Page 2 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 1.1.3 Approaches to Game AI There are many different approaches to Game AI, only some of which will be highlighted here, but all share the goal of facilitating intelligent and autonomous decision-making at runtime (Kirby, 2011). Figure 1 (Millington & Funge, 2012) highlights the general shape of most Game AI systems. Figure 1: General AI model diagram (i) Scripted AI Scripted, or Hard-coded AI, is the most traditional approach, and still the most common. Ranging from simple condition (if-then) statements to more object-oriented, data-driven approaches, it can be simple, fast and effective, with minimal computational overhead and fast execution (Kirby, 2011). As complexity grows however, the code can be exposed as brittle, rigid, unmanageable, and a recipe for unintended artificial stupidity (Kirby, 2011). A critical issue is the limited ability for scripted AI to assess when certain behaviours are appropriate, particularly as size and complexity increase (Kirby, 2011). (ii) Finite State Machines Finite State Machines (FSM), are formal structures to address the issue of program complexity. Figure 2 (Kirby, 2011) is a diagrammatic representation of a simple FSM for determining NPC ‘behaviour’. The circles represent ‘states’, or behaviours, while the arrows represent ‘transitions’ between states. The captions describe the conditions under which transitions will occur. When using FSM it is important to review each transition to ensure that it is “always reasonable”, since as a game progresses, contingencies can occur which are not always obvious in the early stages of play (Kirby, 2011). Complexity arises when the number of states ‘explodes’ to an unmanageable level, inevitably leading to an even bigger explosion of transitions, or when multiple transitions exist out of a single state, producing ambiguities or ‘race conditions’. Race conditions occur when the AI system must deliberate on its next course of action due to a surfeit of ‘correct’ options (Kirby, 2011). One way to deal with race conditions is to use a Hierarchical State Machine (HSM), which prioritizes transitions using a stacking approach (Flórez-Puga, Gómez-Martín, Gómez-Martín, Díaz-Agudo & González-Calero, 2009). Figure 2: Finite State Machine Diagram
    Page 3 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan (iii) Rule-based Systems Rule-based systems consist of a set of rules and a framework to apply them (Kirby, 2011). Each time the AI “thinks”, it examines current state of the same world in accordance with the rules. This system is less constrained than a state-based approach, but it is difficult to plan the perfect rule for every potential scenario, and often several are needed just to cover default behaviours (Kirby, 2011). (iv) Random and Probabilistic Systems Random systems can be effective in simulating real behaviour, which is occasionally unpredictable, but only within appropriate parameters. The choice must be between equally good options to avoid puzzling outcomes which could compromise player experience (Kirby, 2011). Probabilistic systems consider odds in an attempt to balance this issue of predictability versus feasibility. Methods for calculating these odds include the popular Monte Carlo method, precomputing, and ‘faking it’, and often require some initial guesswork to obtain numerical data, which must then be fine-tuned to perfect the system. This ‘tuning’ is the most challenging aspect of building an effective probabilistic system (Kirby, 2011). (v) Machine Learning Machine Learning, using techniques such as genetic algorithms or neural networks, is another approach to Game AI, however to date it has not been used particularly often outside of academic research (Kirby, 2011). Genetic algorithms are suitable for some games, but neural networks are considered too unpredictable in many cases (Kirby, 2011). Game developers, particularly in the area of narrative games, tend to avoid relinquishing authorial control of what happens after release, for fear of unwittingly evoking unforeseen cases of severe artificial stupidity (Rabin, 2013). (vi) Other Approaches Other approaches include, but are not limited to, planning methods such as Stanford Research Institute Problem Solver (STRIPS), Goal Oriented Action Planning (GOAP), & Hierarchical Task Networks (HTN), pathfinding techniques such as the commonly used A* algorithm, and Behaviour Trees, which are the focus of subsequent sections of this paper (Kirby, 2011). 1.2 Decision -Making Decision-making involves a character, or other game AI component, working out what to do next, from a range of possible behaviours (Millington & Funge, 2012). The system calculates the most appropriate behaviour at a given moment, then executes it as shown in Figure 3 (Millington & Funge, 2012). This is the foundation of Game AI. It can be simple, like the farm animals in Zelda games, that are stationary until a player approaches, or complex, like enemies in Half-Life 2 that chain multiple, simultaneous strategies into composite behaviours in order to aggressively pursue even a distant player (Millington & Funge, 2012). Decision making can be simple, for example. farm animals in Zelda games will stand still unless a player approaches closely (Millington & Funge, 2012). In Half-Life 2 however, enemies display complex decision-making by trying a number of different strategies to reach the player, and chaining some of these actions together into composite behaviours (Millington & Funge, 2012).
    Page 4 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan Two factors affecting decision-making are selectors and reasoners (Jadon, Singhal & Dawn, 2014). Selectors use simple logic, like selecting the first option that fits a requirements, or by pre-determined priority. Reasoners dynamically calculate probabilities and often select one of a number of ‘correct’ choices based on several factors (Millington & Funge, 2012). Section 1.1.3 of this paper outlines several different decision-making approaches, and it important to realize they are all essentially doing the same thing – “acting intelligently under changing conditions”, which is Kirby’s definition of Game AI (2011). Figure 4 shows an example of a decision tree, or graphical depiction of decision-making which is simple to read, easy to implement, and fast to execute (Millington & Funge, 2012). Decision trees are modular, easy to create and can range from very simple to extremely sophisticated (Millington & Funge, 2012). It is from decision trees that behaviour trees evolved. Figure 3: Decision Making in Game AI Figure 4: Decision Tree example 1.3 History of Behaviour Trees in Game AI Behaviour Trees first made a splash as the ‘next big thing’ at the 2005 Game Developers Conference (Kirby, 2011). They had already been used in Halo 2 (2004), made another appearance in in Spore (2008), and began to gain ground towards acceptance as a mainstream approach for non-player character (NPC) AI. It was not, however, until Champanard’s (2012) video tutorial on second generation behaviour trees, for aigamedev.com, that stakeholders began to recognize the magnitude of untapped potential for behaviour trees. Since then, despite slow (but steady) progress in commercial game AI, particularly in relation to NPCs, much promising research has been undertaken into utilizing behaviour trees for several other Game AI applications, as well as into developing hybrid AI systems which combine the benefits of behaviour trees with those of other approaches such as HSM. The remainder of this paper addresses the nature and characteristics of, and suitable applications for behaviour trees, and discusses where they might be situated in the near future of Game AI.
    Page 5 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 2. Definitions and Concepts 2.1 What are Behaviour Trees? Behaviour Trees are simple, hierarchical data structures for managing complexity by providing “ a graphical representation and formalization for complex actions (Markowitz, Kider, Shoulson & Bader, 2011). They can be described as a synthesis of HSMs and other AI techniques (Millington & Funge, 2012), such as Planning methods, especially HTNs (Flórez-Puga, et al., 2009). They are more intuitive than state machines (Child & Dey, 2013), and they are used to store and execute plans rather than generate them, as is the case with HTNs (Flórez-Puga, et al., 2009). “BTs can be seen as AND-OR trees that store all possible plans that a game entity … can follow to obtain its goals” (Flórez- Puga, et al., 2009). It is the strict and static hierarchical nature of behaviour trees that makes them amenable to reuse and modularization (Zhao & Szafron, 2014). All behaviour trees are rooted tree structures that are traversed each time the AI logic is executed (Černý, et al., 2015, Ji & Ma, 2013). Trees comprise nodes and branches in parent-child relationships (Kirby, 2011). They can possess any number of levels, but child nodes are restricted to a single parent (Kirby, 2011). Nodes near the root of the tree represent higher-level behaviours that those close to the leaves (Černý, et al., 2015). When the AI cycle runs, a parent node selects an appropriate child node to perform, with a boolean (or still in progress) result (Johansson & Dell’Acqua, 2012) being returned from the child to the parent (Ji & Ma, 2013). Behaviour trees can be seen as goal structures that portray “how a high-level goal can be decomposed into lower level ones until reaching primitive goals that can be achieved by available actions” (Rabin, 2013). Figure 5 shows a simple behaviour tree example for a non-player character (NPC) (Rabin, 2013). Figure 5: Behaviour Tree example As architectures, behaviour trees are unusual in that they can contain other systems (Rabin, 2013). Each node (excepting leaf, or action nodes) is essentially a selector making a small contribution to an overall decision (Rabin, 2013). Recent developments have shown that a selector can contain nearly any other kind of AI approach, making behaviour trees more than architectures; they are in fact frameworks, or meta- architectures (Rabin, 2013).
    Page 6 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 2.2 Components Behaviour tree branches depict the relationships between nodes, which are either composite (high level) nodes, or leaf (low level) nodes (Ji & Ma, 2013). Leaf nodes call various functions to perform and can judge their success or not (Ji & Ma, 2013). They are depicted diagrammatically as rounded white rectangles for action or behaviour nodes, and rounded grey rectangles for condition nodes (Johansson & Dell’Acqua, 2012). Composite nodes start from the top or root node, and select lower (closer to the leaves) nodes to run (Ji & Ma, 2013). There are several types of, or functions for, composite nodes. For example, a Priority Selector node traverses child nodes in order, returning false only if all child nodes return false. If one returns true, it stops the traversal and returns true to its parent node (Ji & Ma, 2013). They are depicted as grey circles containing question marks (Johansson & Dell’Acqua, 2012). A Sequence Selector node traverses child nodes in order, returning true only if all child nodes return true. If one returns false, it stops the traversal and returns false to its parent node (Ji & Ma, 2013). They are depicted as grey squares with arrows (Johansson & Dell’Acqua, 2012). Selector and sequence nodes are both capable of non-linear traversal according to weighted random variants (Ji & Ma, 2013). A Parallel node traverses children in parallel, return a value to the parent node in accordance with specific strategies (Ji & Ma, 2013). They are depicted as grey circles the letter ‘P’ inside (Johansson & Dell’Acqua, 2012). A decorator node behaves like a filter, placing constraints on execution of its (sole) child node without altering its nature (Johansson & Dell’Acqua, 2012). They are depicted as diamonds containing descriptive text (Johansson & Dell’Acqua, 2012). Figure 6 shows a behaviour tree example (for a camera system), which comprises a number of these different node types (Markowitz, et al., 2011). Figure 6: Behaviour Tree example showing several components
    Page 7 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 2.3 Types of Behaviour Trees There are several different types, or interpretations of behaviour trees. These include simple (or first-generation) trees which are evaluated either top down, or bottom up, as well as more complex trees, known as second generation behaviour trees. These are either data or event-driven (Kirby, 2011). 2.3.1 Top Down Evaluation Most behaviour trees are evaluated top down, from root to leaf (Kirby, 2011). In this kind of evaluation, a high level behaviour cannot decide to activate unless it is aware that at least one child wants to activate, and this constraint holds true throughout the entire traversal until at least one usable behaviour is identified (Kirby, 2011). Because they are checked often in this arrangement, high-level nodes need to be fast and efficient (Kirby, 2011). 2.3.2 Bottom Up Evaluation Some behaviour trees are evaluated from the bottom up, or from leaf to root (Kirby, 2011). This requires additional processing power, but if computation is no object, bottom up evaluation has its advantages (Kirby, 2011). This method begins with leaves commenting on the current state, then feed their opinions upwards, providing the higher level nodes with absolute surety of just how much each child wants to activate, leaving them free to prioritize available options, with final selection occurring atop the tree (Kirby, 2011). The trade off for the performance hit is the potential for better, more informed decision-making, allowing for more nuanced behaviour variations (Kirby, 2011). 2.3.3 Second Generation Behaviour Trees As these ‘new-fangled’ behaviour trees began to be used more in game development, more complex instances inevitably occurred, and performance issues began to be noticed (Champanard, 2012). These were the prime motivator for the development of second generation behaviour trees, unveiled by Alex Champanard at a game conference (2012). He categorized these trees as data-oriented and event-driven behaviour trees (Champanard, 2012). Both gain performance boosts for different reasons; data-oriented trees by improving cache coherency, and event-driven trees by minimizing the amount of work undertaken in each traversal (Champanard, 2012). Second generation behaviour trees are discussed further in the Advanced Topics and Trends section (4) of this paper. 2.4 Strengths & Limitations 2.4.1 Strengths In a nutshell, the greatest strengths of the behaviour tree are both its simplicity (Rabin, 2013), and simultaneous capacity for complexity (Kirby, 2011). Behaviour trees are easy to read and understand, even for non-programmer designers (Millington & Funge, 2012). They are relatively easy to debug, allow for sophisticated behaviour selection, and help manage and control complexity (Kirby, 2011). BTs are scalable and modular, and thus reusable. They offer the flexibility to incorporate, and even improve upon (Lim, Baumgarten & Colton, 2010), other AI methodologies “in a way that gives you full control over behaviour and performance” (Rabin, 2013). The composability of behaviour trees into sub-trees to handle more complex actions is a powerful tool (Millington & Funge, 2012). Tasks share an interface (the tree), yet are largely self-contained, and so lend themselves to hierarchies (Millington & Funge, 2012), and extensibility (Rabin, 2013). They are free of the main constraint under which FSMs suffer, that is they do not need to know the transition criteria for all other states (Rabin, 2013). Nor do they need to remember previously running behaviours; in fact behaviours
    Page 8 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan should be independent of each other in order that the tree can be easily modified (Rabin, 2013). All these qualities make behaviour trees extremely powerful tools. 2.4.2 Limitations Useful as they are, behaviour trees are not always the best solution for every situation (Millington & Funge, 2012). For example, while they work well for binary decisions, things can get complicated and cumbersome when the need arises to respond to external events such as changing strategies based on low ammunition stocks (Millington & Funge, 2012). This is where hybrid systems come in, such as including tasks in the tree that resemble state machines (Millington & Funge). While behaviour trees are great at modeling what an AI can do, the fact that priority is static means they are not always as successful at specifying what an AI should do. They may require intimate knowledge of the world-state (Rabin, 2013), which can lead to a plethora of dependencies on other, changing systems (Rabin, 2013). Rabin (2013) gives an example of a case where a planning system may be more suitable than a behaviour tree: Since behaviors themselves are stateless, care must be taken when creating behaviors that appear to apply memory. For example, imagine a citizen running away from a battle. Once well away from the area, the “run away” behavior may stop executing, and the highest-priority behavior that takes over could take the citizen back into the combat area, making the citizen continually loop between two behaviors. While steps can be taken to prevent this sort of problem, tradit- ional planners can tend to deal with the situation more easily. Additionally, since most behaviour trees traverse in full extremely often, processing speed can sometimes be an issue when compared with FSMs (Rabin, 2013). Figure 7 shows a table summarising some of the potential strengths and limitations of behaviour trees. Table 1: Behaviour Trees – Summary of Potential Strengths & Limitations
    Page 9 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 3. Applications As behaviour trees become more embedded in standard game development practice, new hybridization techniques with other systems are imagined, and new applications to which they are suited are frequently discovered. This paper details just a few of the established, and myriad emerging Game AI applications for behaviour trees. 3.1 Non-Player Characters By far the most common application for which behaviour trees are utilized to date is AI for non-player characters (NPCs) (Johansson & Dell-Acqua, 2012). Their use for controlling basic opponent behaviours is especially common, but they can also contribute to player immersion by guiding more complex and lifelike character behaviours (Pedica & Vilhjálmsson, 2012). 3.1.1 Opponent AI Opponent NPC AI generally performs three basic functions – moving NPCs, deciding where to move, and tactical thinking (Millington & Funge, 2012), from a range of behaviours such as attack, rest, hide, explore and patrol (Millington & Funge, 2012). One example that both utilizes behaviour trees, and demonstrates how they can incorporate other systems, is a military simulator ‘lifelike bots’ project (Jadon, et al, 2014). Each behaviour tree level represents a state, with dynamic parameters calculated by utility-based reasoners (rather than selectors) at run time (Jadon, et al., 2012). Transitions between levels occur in accordance with a “global parameter force”, which increases when suspicious or threat activity is present (Jadon, et al., 2014). A relatively passive Patrol state is the default, with a traditional subtree governing variations such as resting or chatting (Jadon, et al., 2014). When the aforementioned force reaches a cthreshold in response to footsteps, rustling leaves, gunfire or similar, aggressive behaviours are exhibited until the force value drops below threshold, and patrol mode is resumed (Jadon, et al., 2014). Anytime an enemy s within NPC field of vision, force value stops decreasing (Jadon, et al., 2014). 3.1.2 AI-controlled players A second ‘bot’ project, this time working with the DEFCON game (real-time strategy based on one-on-one conflict), includes an avatar feature whether an AI-controlled player can stand in for a temporarily absent real player, as well as competitive bots to compete against human players (Lim, Baumgarten & Colton, 2010). It applies evolutionary algorithms to behaviour trees for individual behaviours to build a competitive NPC that, more often not, can beat DEFCON’s existing hard-coded bot, demonstrating that behaviour trees can successfully incorporate evolutionary techniques to develop capable automated players (Lim, Baumgarten & Colton, 2010). 3.1.3 More complex NPC behaviours From animals which exist as decoration or to be hunted, to fully fleshed out companion characters, NPCs follow a “Sense-Think-Act cycle”, with the thinking part open to a broad range of implementations (Rabin, 2013). (i) Behaviour Objects In Open World Games with numerous NPCs, subtrees often define behaviour subroutines for reuse, subject to the normal limitations of behaviour trees (Černý, et al., 2015). A project to overcome these limitations utilizes ‘Behaviour Objects’, inspired by Object-Oriented Programming, with data and methods replaced by a brain (data and decision logic), and behaviours (Černý et al., 2015). Behaviour executes in its context,
    Page 10 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan accessing NPC internal state, whereby the NPC ‘holds’ the behaviour (Černý et al., 2015). The behaviour can still access the object’s instance data, providing further context and a channel of implicit communication with other NPCs exhibiting behaviour from the same instance (Černý et al., 2015). (ii) Emotional decision-making Predictable, unadaptive decision-making can equal a lack of player immersion. Johansson & Dell’Acqua tackle this issue by extending behaviour trees to incorporate emotions into decision-making (2012). They argue that emotions “are vital for human decision-making”, and that traditional behaviour trees that incorporate realistic emotions into conditions would be overly-nested and cumbersome (Johansson & Dell’Acqua, 2012). They claim to solve this issue using a new type of priority selector - an emotional selector – with dynamically evaluated priorities allowing for emotional influence (Johansson & Dell’Acqua, 2012). The selector incorporates timing, risk perception and planning as decision-making factors most influenced by emotion (Johansson & Dell’Acqua, 2012). The emotional selector alters child node priorities at runtime in response to emotions (Johansson & Dell’Acqua, 2012). (iii) Prioritizing Behaviours In behaviour trees most action possess a primary goal and some additional goals depending on context (Flórez-Puga et al., 2009). Goal hierarchies that determine behaviour based on reasoning at different levels of abstraction are crucial, since just focusing on the primary goal can lead to artificial stupidity if, for example, reaching a destination, even while being attacked, supersedes the need to survive (Flórez-Puga et al., 2009). Staying alive needs to be higher up the hierarchy, so that if survival behaviour is activated, the tree branch being executed (reach destination) can be pruned (Flórez- Puga et al., 2009). Flórez-Puga et al. (2009) dynamically combine behaviour trees with a Case-Based Reasoning (CBR) approach using Query Behaviour Trees (QBTs) as an ideal midpoint between the two methodologies. The CBR system is queried at runtime, retrieving the most appropriate behaviour from the case base of designed behaviours (Flórez-Puga et al., 2009). (iv) Social Territorial Intelligence Pedica & Vilhjálmsson (2012) integrate behaviour trees with reactivity for social territoriality in NPCs. Their system allows simultaneous running and blending of multiple branches (Pedica & Vilhjálmsson, 2012). An arbitrational midlayer performs blending prior to activation, and branches are prioritised in order that high priority can subsume low priority where goals conflict (Pedica & Vilhjálmsson, 2012). They claim the result is extensible and reusable, with responsive, smooth continuity of motion, and new levels of social behaviour realism incorporating equality, personal distance, cohesion, and common attention (Pedica & Vilhjálmsson, 2012). Figure 8 shows four steps to social group dynamics. Step (a) shows a passerby is noticed when the territory is entered, and in turn a group member notices them being noticed. Step (b) shows the passerby invited to join the group. Step (c) shows the new member welcomed with a glance. Step (d) shows the group making physical room for the newcomer (Pedica & Vilhjálmsson, 2012).
    Page 11 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan Figure 7: Social group dynamics simulation Figure 9 summarises the architecture. Diagram (a) represents different action requests to control various body parts. Diagram (b) shows the blending process, where requests are grouped by type, combined and “packed into a motivation” (Pedica & Vilhjálmsson, 2012). Diagram (c) shows the motivation being sent to an interface for rendering action (Pedica & Vilhjálmsson, 2012). Figure 8: Architecture 3.2 Intelligent camera control Camera systems for virtual worlds tend to produce fairly basic animations, when compared with the robust storytelling features of real cinematography (Markowitz, Kider, Shoulson & Badler, 2011). An intelligent camera system, using behaviour trees to automatically place, aim, pan, tilt and zoom the camera, and to track events in real time, is presented by Markowitz et al. (2011). Behaviour trees describe how an intelligent camera might behave, “from low-level narrative elements assigned by ‘smart events’” (Markowitz et al., 2011). Hierarchical subtrees encapsulate nodes for controlling particular camera semantics, a modular and reusable approach capable of complexity of style and transition (Markowitz et al., 2011). A director can optionally adjust settings in real time (Markowitz et al., 2011). Smart events store behaviour data (responses, parameters) and update behaviour tree parameters, a message board updates global data for the evolving event, and a blackboard updates local information for the behaviour tree (Markowitz et al., 2011). A smart event broadcasts to the message board and assigns a free camera, or prioritises events when all cameras are busy (Markowitz et al., 2011). They claim the result is “a high-quality visual experience to the player, thereby turning the game into the visual experience of a movie” (Markowitz et al., 2011). Figures 10 and 11 show basic camera movement controls, and an intelligent camera behaviour tree, respectively (Markowitz et al., 2011).
    Page 12 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan Figure 9: Basic cinematography movement controls Figure 10: An intelligent camera behaviour tree 3.3 Interactive storytelling Automated narration tools for emergent storytelling is a growing trend, and Kapadia, Falk, Zünd, Marti, Sumner, & Gross, 2015) present a new formalism to this purpose, called Interactive Behaviour Trees (IBTs). Their aims are to enable designers to easily create complex, multi-arc, branching stories in a modular and extensible way, and to allow players more agency in their interactions within the game world (Kapadia et al., 2015). This is achieved by decoupling player input monitoring, narrative, and player influence on story, which facilitates both player freedom and content creation (Kapadia et al., 2015). The behaviour trees encompass a set of tools to detect and resolve narrative inconsistencies and conflicts, empowering the content creator to focus on the stories rather than interactivity integration, which is automated (Kapadia et al., Feb 2015). These tools can also dynamically detect and resolve story issues at runtime in response to player intervention (Kapadia et al., 2015).
    Page 13 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 4. Advanced Topics and Trends 4.1 Advanced Behaviour Trees Many of the application examples seen thus far in this paper have been hybridized examples of behaviour trees as meta-architectures, encompassing other AI architectures in various kinds of symbiotic feedback loop, or modifying traditional nodes types. They include utility-based reasoning (Jadon, et al., 2014), evolutionary algorithms (Lim, Baumgarten & Colton, 2010), a kind of object-oriented state machine system (Černý et al., 2015), an emotional variation on priority selectors (Johansson & Dell’Acqua, 2012), case-based reasoning with query behaviour trees (Flórez-Puga et al., 2009), reactivity with midlayer blending (Pedica & Vilhjálmsson, 2012), smart events for cinematography (Markowitz et al., 2011), and decoupling of narrative components for modular and emergent storytelling (Kapadia et al., Feb 2015). Some of these example can be considered second-generation behaviour trees, which were briefly touched on earlier and will now be discussed in slightly greater detail. Data-oriented behaviour trees benefit from improved cache coherency (Champanard, 2012). Traditional trees access memory at many different locations (pointers), that point to child nodes (Champanard, 2012).With scaling, this becomes a slow system (Champanard, 2012). By pre-allocating a behaviour tree buffer and placing nodes in the buffer, a data-oriented tree improves scalability and cache performance (Champanard, 2012). Event-driven behaviour trees benefit from reducing the work done each time the tree is updated (Champanard, 2012). When a node status is returned, the tree stores which node is currently executing (Champanard, 2012). In this way it is able to return directly to this node on the next update, avoiding the need for a full tree traversal and minimising the tree’s workload (Champanard, 2012). 4.2 The Commercial-Academic Gap The approximately decade-long existence of behaviour trees has coincided with both large strides in console and PC graphics and processing power, and a subsequent industry focus on increasing AI sophistication to match growing player expectations of the gaming experience (Flórez-Puga et al., 2009). During this period, industry has taken more of an interest in academic AI research “to provide rich, robust, and scalable techniques” for NPCs, narrative schemes and, slowly, other applications (Flórez-Puga et al., 2009). Academia has reciprocated that interest, yet a large gap still exists between common commercial practice and cutting edge academic AI (Flórez-Puga et al., 2009), perhaps due to a profit-motivated wariness of venturing away from tried and true approaches (Černý et al., 2015). While it seems research areas like machine learning are trying, without overwhelming success, to drive industry practice in new directions, Flórez- Puga et al. (2009), when presenting their query-based, cased-based reasoning- behaviour tree hybrid, managed to emphasise player experience without compromising designer authorial control, a game design fundamental that industry seems unwilling to relinquish. It will be interesting to see what the near future holds for the commercial- academic Game AI relationship, as machine learning and data mining inevitably saturate so many other areas of technology, and how innovative and playable forthcoming games will be as a result.
    Page 14 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan 4.3 Future Trends While it is difficult to predict exactly what even the near future will look like for Game AI and behaviour trees, particularly in the commercial arena, it is clear that hybrid trees’ simple approach to encapsulating the inner complexities of other systems will continue to develop, as designers and academics try and refine new combinations and ideas. It also seems certain that the recent focus on emergent behaviour in games will continue to influence AI, but will need to balance new developments with the high value designers and quality controllers place on control and predictability (Kirby, 2011). Two recent projects may provide some clue as to what kinds of developments can be expected. Traditional behaviour trees are accessible tools for non-programming designers, yet the hybrid forms, which utilize other approaches, can require more technical expertise to decipher (Child & Dey, 2013). Q-Learning behaviour trees (QL-BTs) are a method for teaching behaviour tree design via the application of reinforcement learning, developed by Child & Dey (2013). QL-BTs facilitate the use of behaviour trees by helping designers to identify optional execution times for each branch, and by providing tools for analysis, debugging, and optimization for early tree prototypes (Child & Dey, 2013). Zhao & Szafron (2014) take second-generation behaviour trees a step further by using behaviour trees with a high level cyclic scheduler to create natural-looking behaviours by determining general NPC objectives, and roles to satisfy those objectives. They argue that NPCs are more convincing when, rather than just standing around when inactive, they interact with each other in realistic ways (Zhao & Szafron, 2014). They achieve this by creating inherently cyclical daily schedules for NPCs, adapting second-generation trees to an explicit temporal model, to simulate the time-based ways that people organize their activities in the real world (Zhao & Szafron, 2014). 5. Conclusion This paper examines behaviour trees, including what they are, how they work, when they are useful, and where they are situated within the broader field of Game AI and its established methodologies. It provides examples of traditional, hybrid and novel behaviour tree systems, and considers their strengths and limitations as design tools. While acknowledging that (notwithstanding widespread use for NPC AI), not all potential applications for behaviour trees have permeated industry to the fullest, this paper concludes that behaviour tree research innovations will continue to influence future commercial game development. Despite their limitations (with regard to Boolean-only logic), behaviour trees are easy to implement and visualize, compatible with almost all other approaches, and are eminently adaptable (Rabin, 2013). Overall, behaviour trees have been a win for Game AI (Millington & Funge, 2012). While innovative academics continue to experiment with their own approaches to overcoming the limitations of behaviour trees, and use them to drive the state of the art forward, developers will, at their own pace, continue to explore the vast potential of behaviour trees (Millington & Funge, 2012).
    Page 15 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan Figures: Figure 1: General AI model diagram (Millington & Funge, 2012) Figure 2: Finite State Machine Diagram (Kirby, 2011) Figure 3: Decision-making in Game AI (Millington & Funge, 2012) Figure 4: Decision Tree Example (Millington & Funge, 2012) Figure 5: Behaviour Tree Example (Rabin, 2013) Figure 6: Behaviour Tree Example Showing Several Component Types (Markowitz, Kider, Shoulson, & Badler, 2011) Figure 7: Social Group Dynamic Simulation (Pedica, & Vilhjálmsson, 2012) Figure 8: Architecture (Pedica, & Vilhjálmsson, 2012) Figure 9: Basic Cinematography Movement Controls (Markowitz et al., 2011) Figure 10: An Intelligent Camera Behaviour Tree (Markowitz et al., 2011)
    Page 16 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan Tables: Table 1: Behaviour Trees – Summary of Potential Strengths and Limitations
    Page 17 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan References: Černý, M., Plch, T., Marko, M., Gemrot, J., Ondráček, P., & Brom, C. (2015). Using Behavior Objects to Manage Complexity in Virtual Worlds. arXiv preprint arXiv:1508.00377. Champanard, A. (2012). Understanding the second-generation of behavior trees. Tillgänglig på internet: http://aigamedev.com/insider/tutorial/second-generation- bt.[Hämtad: 14.04. 06]. Child, C. H. T. & Dey, R. (2013). QL-BT: Enhancing Behaviour Tree Design and Implementation with Q-Learning. 2013 IEEE Conference on Computational Intelligence in Games (CIG), 275- 282. Flórez-Puga, G., Gómez-Martín, M. A., Gómez-Martín, P. P., Díaz-Agudo, B., & González-Calero, P. A. (2009). Query-enabled behavior trees. IEEE Transactions on Computational Intelligence and AI in Games, 1(4), 298-308. Jadon, S., Singhal, A., & Dawn, S. (2014). Military Simulator-A Case Study of Behaviour Tree and Utility based architecture. arXiv preprint arXiv:1405.7944. Ji, L. X., & Ma, J. H. (2014, May). Research on the Behavior of Intelligent Role in Computer Games Based on Behavior Tree. In Applied Mechanics and Materials (Vol. 509, pp. 165-169). Johansson, A., & Dell'Acqua, P. (2012, September). Emotional behavior trees. In Computational Intelligence and Games (CIG), 2012 IEEE Conference on (pp. 355-362). IEEE. Kapadia, M., Falk, J., Zünd, F., Marti, M., Sumner, R. W., & Gross, M. (2015, February). Computer-assisted authoring of interactive narratives. In Proceedings of the 19th Symposium on Interactive 3D Graphics and Games, i3D (Vol. 15, pp. 85-92). Kirby, N. (2011). Introduction to game AI. Cengage Learning Boston, MA, USA. Lim, C. U., Baumgarten, R., & Colton, S. (2010). Evolving behaviour trees for the commercial game DEFCON. In Applications of evolutionary computation (pp. 100-110). Springer Berlin Heidelberg. Markowitz, D., Kider Jr, J. T., Shoulson, A., & Badler, N. I. (2011). Intelligent camera control using behavior trees. In Motion in Games (pp. 156-167). Springer Berlin Heidelberg. Millington, I., & Funge, J. (2012). Artificial intelligence for games. Morgan Kaufmann Burlington, MA, USA. Pedica, C., & Vilhjálmsson, H. H. (2012, August). Lifelike interactive characters with behavior trees for social territorial intelligence. In ACM SIGGRAPH 2012 Posters (p. 32). ACM. Rabin, S. (Ed.). (2013). Game AI Pro: Collected Wisdom of Game AI Professionals. CRC Press Boca Raton, FL, USA.
    Page 18 of 19 A Survey of Behaviour Trees and their Applications for Game AI Kim McQuillan *Robertson, G., & Watson, I. (2015, September). Building behavior trees from observations in real-time strategy games. 2015 International Symposium on Innovations in Intelligent Systems and Applications (INISTA), 1-7. IEEE. *Shoulson, A., Garcia, F. M., Jones, M., Mead, R., & Badler, N. I. (2011). Parameterizing behavior trees. In Motion in Games (pp. 144-155). Springer Berlin Heidelberg. Zhao, R., & Szafron, D. (2014). Virtual Character Behavior Architecture using Cyclic Scheduling. In Proceedings of the 9th International Conference on the Foundations of Digital Games (FDG 2014).